Sobre la forma normal de Chomsky
Donada una gramàtica incontextual G, descriviu un procediment de temps polinòmic per construir una gramàtica G' que generi el mateix llenguatge que G i que estigui en forma normal de Chomsky.
Donada una gramàtica G en forma normal de Chomsky i un mot w generat per G, en quantes passes es produeix w? (en funció de |w|)
Recordeu que una gramàtica incontextual G està en forma normal de Chomsky si totes les seves produccions són de la forma:
\begin{aligned} A &\to BC, \text{o} \\ A &\to a, \text{o} \\ S &\to \lambda, \end{aligned} on A, B i C són símbols no terminals, a és un símbol terminal i S és el símbol inicial. A més, ni B ni C poden començar pel símbol S i la producció S\to \lambda només pot aparèixer si \lambda és al llenguatge generat per G.